Not applicable.
Not applicable.
The present invention generally relates to the orderly and efficient transfer of data and instructions on computer bus systems. More particularly, the present invention relates to an arbitration system that enables bus devices that have the greatest need to access the bus. Still more particularly, the present invention relates to a bus arbitration system that adaptively grants priority to devices on the bus based on the workload of the devices.
A personal computer system includes a number of components with specialized functions that cooperatively interact to enable the computer system to perform a variety of tasks. The ability of these various components to exchange data and other signals is vital to the successful operation of a computer system. Typically, components interact by reading or writing data or instructions to other components in the system.
Early computer systems typically included a processor (or CPU), random access memory (RAM), and certain peripheral devices such as a floppy drive, a keyboard and a display. These components typically were coupled together using a network of address, data and control lines, commonly referred to as a xe2x80x9cbus.xe2x80x9d As computer technology evolved, it became common to connect additional peripheral devices to the computer through ports (such as a parallel port or a serial port), or by including the peripheral device on the main system circuit board (or xe2x80x9cmotherboardxe2x80x9d) and connecting it to the system bus.
The computer operates by having data flow through the system, with modification of the data occurring frequently. Traditionally, the CPU controlled most activities in the computer system. The CPU supervises data flow and is responsible for most of the high-level data modification in the computer. The CPU, therefore, is the xe2x80x9cheartxe2x80x9d of the system and receives signals from the peripheral devices, reads and writes data to memory, processes data, and generates signals controlling the peripheral devices.
Despite the importance of the processor, the performance of the computer system is determined only in part by the speed and efficiency of the processor. Other factors also affect system performance. One of the most critical factors is the bus that interconnects the various system components. The size and clock speed of the bus dictate the maximum amount of data that can be transmitted between components. Early bus systems, such as the ISA (Industry Standard Architecture) bus, required that all components communicate through the CPU. The ISA bus, as the name implies, was a bus standard adopted by computer manufacturers to permit the manufacturers of peripheral devices to design devices that would be compatible with most computer systems.
Since the introduction of the ISA bus, computer technology has continued to evolve at a relatively rapid pace. New peripheral devices have been developed, and processor speeds and the size of memory arrays have increased dramatically. In conjunction with these advances, designers have sought to increase the ability of the various system busses to transfer more data at a faster speed. One way in which the system busses have been made more efficient is to permit data to be exchanged in a computer system without the assistance of the CPU. To implement this design, however, a new bus protocol had to be developed. One of the first such buses that permitted peripheral devices to run master cycles independently of the CPU was the EISA (Extended Industry Standard Architecture) bus. The EISA bus enables various system components residing on the EISA bus to obtain mastership of the bus and to run cycles on the bus.
More recently, the Peripheral Component Interconnect (PCI) bus has become increasingly popular. Like the EISA bus, the PCI bus has bus master capabilities, and thus certain master components residing on the PCI bus may communicate directly with other PCI components by addressing read and write commands to these other components based on protocols defined in the PCI Specification, which has been jointly developed by companies in the computer industry. Because of the bus mastering capabilities and other advantages of the PCI bus, many computer manufacturers now implement the PCI bus as one of the primary expansion busses in the computer system.
FIG. 1 shows a representative prior art computer system that includes a CPU 20 coupled to a bridge logic device 25 via a CPU bus 23. The bridge logic device 25 is sometimes referred to as a xe2x80x9cNorth bridgexe2x80x9d for no other reason than it often is depicted at the upper end of a computer system drawing. The North bridge 25 also couples to the main memory array 35 by a memory bus 30. The North bridge 25 couples the CPU 20 and memory 35 to the peripheral devices 42, 44 in the system through a PCI bus 45 or other expansion bus. Various components that understand PCI protocol may reside on the PCI bus such as PCI bus devices 42, 44. PCI devices may comprise any of a number of different peripheral devices including video accelerators, audio cards, hard or floppy disk drives, Small Computer Systems Interface (SCSI) adapters and the like.
If other secondary expansion busses 47, 51 are provided in the computer system, another bridge logic device 40 typically is used to couple the system bus 45 to those expansion busses. This bridge logic device 40 is sometimes referred to as a xe2x80x9cSouth bridgexe2x80x9d reflecting its location vis-a-vis the North bridge in a typical computer system drawing. An example of such bridge logic is described in U.S. Pat. No. 5,634,073, assigned to Compaq Computer Corporation. In FIG. 1, the South bridge 40 couples the PCI bus 45 to an ISA bus 49 and a USB bus 51. Various ISA-compatible devices 49 may be coupled to the ISA bus 47. As one skilled in the art will understand, devices residing on the ISA bus 47 or USB bus 51 may be targets for devices coupled to the PCI bus 45, including the CPU 20. Thus, even though the CPU 20 is not directly connected to the ISA bus 47, it may still need to read and write data, or perform other operations, to devices on that bus. The PCI protocol permits devices residing on the PCI bus to run master cycles to targets on the PCI bus. To permit devices on other busses to run master cycles on the PCI bus, the South bridge 40 operates as a master device on the PCI bus 45 to execute transactions that actually originate on the secondary expansion bus, such as the ISA bus 49.
Because there may be numerous master devices residing on expansion busses, such as the PCI bus, typically a bus arbiter 27 is provided in the computer system. When multiple devices seek to access the bus at the same time, the bus arbiter 27 determines which of these devices will be granted the right to run cycles on the bus. Thus, the bus arbiter receives request (REQ) signals from devices on the bus, and issues a grant (GNT) signal to a particular device based on a predetermined priority scheme, indicating that the recipient of the grant signal may run a cycle on the PCI bus 45. Two priority schemes are commonly used in the bus arbiter 27. The first scheme is to assign a predetermined priority level to each device on the bus, so that when two devices issue a request to run a cycle on the bus simultaneously, the bus arbiter assigns grants access to the bus based on the pre-assigned level. A second common scheme is to award priority on a round-robin basis, where the bus arbiter 27 essentially takes turn awarding priority to each device. The problem with these arbitration schemes is that they fail to consider other events that may impact efficiency of the bus. In particular, these arbitration schemes may cause a bus device to be xe2x80x9cstarvedxe2x80x9d by not obtaining sufficient access to run requisite bus cycles. Other schemes have also been proposed over the years in an attempt to increase the efficiency of bus transfers. See for example U.S. Pat. No. 5,907,689, entitled xe2x80x9cMaster-Target Based Arbitration Priority,xe2x80x9d assigned to the assignee of the present invention. One common problem with existing prior bus arbitration designs is that they fail to consider the workload of the devices on the bus. As a result, a device that has a large workload may be unable to obtain access to the bus to complete operations that are awaiting execution.
It would be desirable is a bus arbitration system was available that would consider the workload of devices when awarding access to a bus. Despite the apparent advantages such a system would offer, to date no such system has been made available.
The present invention solves the deficiencies of the prior art by implementing an adaptive bus arbiter that monitors the workload of devices that are requesting access to a bus. According to the preferred embodiment, the bus arbiter receives request signals from devices on the bus seeking to run cycles on that bus. In addition, the bus arbiter also receives a signal from each requesting device indicating the workload of that device. In accordance with the preferred embodiment, each of the bus devices includes a queue in which operations that are awaiting execution are stored. The workload of a particular device preferably is based on the number of operations that are in that queue""s device, awaiting execution. Each device thus sends a signal to the bus arbiter indicating the number of operations that are awaiting execution in its queue. The workload signal may comprise a multi-bit signal to indicate the exact number of pending operations (for example, there are four operations pending in the queue), or may use ranges (for example, there are three or more operations pending in the queue).
In response to receipt of a request signal and a workload signal, the bus arbiter determines priority among conflicting bus requests by considering the workload of each device seeking to run a bus cycle. According to the preferred embodiment, the bus arbiter grants priority to the device that has the most operations pending in its queue, or if two devices have the same number or range of entries, based on a combination of pending entries and other factors. In one exemplary embodiment, the bus arbiter permits the bus device that is awarded priority to execute all pending operations in its queue. According to an alternative embodiment, the bus arbiter re-determines priority on a cycle-by-cycle basis.
These and other details regarding the present invention will become apparent to one skilled in the art, upon analyzing the following detailed description of the preferred embodiment, drawings and claims.